package HashBuck;


/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2024-05-26
 * Time: 17:09
 */
public class HashBuck {
    static class Node{
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
     public Node[] array = new Node[10];
     public int usedSize;
     public void push(int key ,int value){
         Node node = new Node(key,value);
         int index = key % array.length;
         Node cur = array[index];
         while(cur != null){
             if(cur.key == key) {
                 //更新value
                 cur.val = value;
                 return;
             }
             cur = cur.next;
         }
         node.next = array[index];
         array[index] = node;
         usedSize++;
         //重新哈希
         if(usedSize*1.0 / array.length >= 0.75){
             reSize();
         }

     }
     private void reSize(){
         Node[] newArray = new Node[array.length*2];
         for (int i = 0; i < array.length; i++) {
             Node cur = array[i];
             while(cur != null){
                 int index = cur.key % newArray.length;
                 Node curNext = cur.next;
                 cur.next = newArray[index];
                 newArray[index]  = cur;
                 cur =curNext;
             }


         }
         array = newArray;


     }
     public int get(int key){
         int index = key % array.length;
         Node cur = array[index];
         while(cur != null){
             if(cur.key == key){
                 return cur.val;
             }
             cur = cur.next;
         }
//         return  -1;
         throw  new ArrayIndexOutOfBoundsException(" 未找到 : "  + key);
     }

}
